# this example by default demonstrates triangulation on torus, using nine copies
# of the points. comment out the 'torus' sections to draw normal triangulation

from itertools import chain, islice
from random import randint

from pygame import display, draw, event, Rect, time
from pygame.locals import *

from pydelaunay import DG, VG, vsearch, dPoint


W, H = 900, 540
SCREEN = display.set_mode((W, H))

AMBER = 255, 126, 0
BLUE = 0, 0, 255
BRIGHT_GREEN = 102, 255, 0
BURNT_ORANGE = 204, 85, 0
CELESTE = 0, 191, 255
DARK_VIOLET = 148, 0, 211
GRAY = 128, 128, 128
GREY = GRAY
RED = 255, 0, 0
SEA_GREEN = 46, 139, 87
WEB_VIOLET = 238, 130, 238
WHITE = (255, 255, 255)

CELL_SIZE = 30
N, M = W / CELL_SIZE, H / CELL_SIZE


# utilities ###################################################################
def memoize(f):
    #memoization decorator for a function taking a single argument
    class memodict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret 
    return memodict().__getitem__

def window(seq, n=2):
    "Returns a sliding window (of width n) over data from the iterable"
    "   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   "
    it = iter(seq)
    result = tuple(islice(it, n))
    if len(result) == n:
        yield result    
    for elem in it:
        result = result[1:] + (elem,)
        yield result


# main ########################################################################
def randpoints(Q, n=9):
    X, Y = zip(*Q)
    xmin, xmax, ymin, ymax = min(X)+1, max(X)-1, min(Y)+1, max(Y)-1
    P = [] # input points
    while len(P) < n:
        p = randint(xmin, xmax), randint(ymin, ymax)
        if not p in P: P.append(p)
    while p in P: p = randint(xmin, xmax), randint(ymin, ymax)
    p = dPoint(True, *p) # input: vsearch point
    return P, p

def draw_grid(surf, cell_size):
    w, h = surf.get_size()
    wr, hr = w % cell_size, h % cell_size
    for x in range(wr, w-wr, cell_size): draw.line(surf, GRAY, (x, hr), (x, h-hr))
    for y in range(hr, h-hr, cell_size): draw.line(surf, GRAY, (wr, y), (w-wr, y))
    draw.rect(surf, GRAY, Rect(wr, hr, w-wr, h-hr), 1)

def draw_points(surf, P):
    w, h = surf.get_size()
    for p in P: draw.circle(surf, DARK_VIOLET, p, 3)

def draw_Tlines(surf, T):
    S = set()
    for t in T:
        for E in window(t+(t[0],)):
            if frozenset(E) in S: continue
            p, q = [(p.x, p.y) if p.isreal else None for p in E]
            if not (p and q): continue
            draw.aaline(surf, BRIGHT_GREEN, p, q)
            S.add(frozenset(E))

def draw_Vlines(surf, V):
    S = set()
    for b in V:
        if b in S: continue
        p, q = [(p.x, p.y) for p in b]
        draw.aaline(surf, BURNT_ORANGE, p, q)
        S.add(b)


if __name__ == '__main__':
    N, M = N / 3, M / 3 # ...to tile P into nine copies

    Q = [(0, 0), (N, 0), (N, M), (0, M)]
    P, p = randpoints(Q)

    # prepare clip for center copy
    clip = [(x + N, y + M) for x, y in Q]
    X, Y = zip(*clip)
    xmin, xmax, ymin, ymax = [
        n * CELL_SIZE for n in (min(X), max(X), min(Y), max(Y))]
    clip = Rect(xmin, ymin, xmax-xmin, ymax-ymin)
    #SCREEN.set_clip(clip)

    # prepare copies
    Q = [(3*x, 3*y) for x, y in Q]
    P = list(
        chain(*[[(x, y),      (x + N, y),       (x + 2*N, y),
                (x, y + M),   (x + N, y + M),   (x + 2*N, y + M),
                (x, y + 2*M), (x + N, y + 2*M), (x + 2*N, y + 2*M)]
               for (x, y) in P]))

    # scale P, Q to screen size
    P = [(x * CELL_SIZE, y * CELL_SIZE) for (x, y) in P]
    Q = [(x * CELL_SIZE, y * CELL_SIZE) for (x, y) in Q]

    # triangulate
    D = DG(P, Q)
    V = VG(D)

    # graph
    Tlines = set([t for t in D.node if not D.successors(t)])
    Vlines = [v for t in V.node for v in V.node[t].values()]
    Vlines = reduce(lambda b0, b1: b0.union(b1), Vlines)
    draw_grid(SCREEN, CELL_SIZE)
    draw_Tlines(SCREEN, Tlines)
    draw_Vlines(SCREEN, Vlines)
    draw_points(SCREEN, P)
    draw.rect(SCREEN, CELESTE, clip, 1) # frame center copy of torus

    # display and interact
    clock = time.Clock()
    while 1:
        clock.tick(40)
        for ev in event.get():
            if ev.type == KEYDOWN:
                if ev.key == K_q: exit()
            if ev.type == MOUSEBUTTONDOWN:
                x, y = ev.pos
                #x, y = (x % clip.w) + clip.x, (y % clip.h) + clip.y
                p = dPoint(True, x, y)
                s = vsearch(p, D, V)
                draw.circle(SCREEN, WHITE, (s.x, s.y), 3)
            if ev.type == MOUSEBUTTONUP: draw.circle(SCREEN, DARK_VIOLET, (s.x, s.y), 3)
        display.flip()

# still some issues with crossover.  maybe orientation of b in B not appropriate?
# when two cc equal, causing problems (false negative site tests)
# the side with two equal cc is automatically successful,
#   so then a querry point need pass one other side test, and this allows the false negs
